Some data needed by computer applications are expensive to create or to access. The expenses can include computational resources to calculate the data and transportation costs (including bandwidth and time) to access the data over a network. Often, a computing device, after once expending resources to create or access these data, will store the data in a “cache” memory. Then, if the computing device again needs the data, they can be accessed inexpensively from the cache.
The cache can be local to the original application or to the original computing device, or it can be shared among several applications and devices. The latter type of cache is often called a “central” cache. In some environments, each application supports a local cache for its own use while sharing a central cache with other applications. The central cache is optimized for storing data useful to more than one application, while the local caches are available to provide the benefits of caching for those data specific to each application.
Managing data in a central cache is rarely straightforward. Multiple applications attempting to read data from the central cache rarely cause difficulties, but the same cannot be said when at least one application wishes to add data to the cache. If other applications are allowed to read from the central cache at the same time that one application is writing to the cache, then the readers can get out-of-date, or even garbled, data. This access coordination problem is exacerbated when more than one application wishes to add data to the cache.
A common approach to ameliorating this access coordination problem is called “cache locking.” Whenever one application wishes to change the contents of the cache, by adding, deleting, or modifying its contents, it seeks sole access to a “lock” data structure. While it has the lock, the writer application can modify the cache, and other applications are prevented from accessing the cache as long as a writer has the lock. Thus, readers are prevented from getting out-of-date or garbled data. If two applications both wish to modify the cache, then one of them must wait until the other relinquishes the lock.
Locks can be quite useful in coordinating access to a central cache. However, it is apparent that they delay access for all applications whenever one application wishes to modify the cache. For some central caches, applications readily tolerate this slowdown. For other caches, however, it can be a real nuisance. For example, consider a font-glyph cache. Characters displayed on a computer screen are made up of individual elements called “glyphs.” As some of these glyphs contain a significant amount of data, and as some of the glyphs consume significant computational resources in their generation, they are ideal subjects for a central cache. However, locking the font-glyph cache while a new glyph is added to it can cause a noticeable delay in an application writing to the computer's screen.
When the memory resources available to a central cache are limited, another cache management issue arises. Multiple applications wishing to add data to the cache operate independently of one another. Thus, none of these applications has a “global” view as to which data should be added to the central cache in order to improve the operating environment generally. The same issue arises when the central cache grows too large and is reformulated in a smaller size in order to allow for further additions. No one application can decide which data should be retained in the central cache and which data are best removed in order to free up memory for future cache growth.